Day 10 : 線性規劃問題(續)

第 11 屆 iThome 鐵人賽

DAY 10

AI & Data

連接數學與現實世界的橋樑 -- 數學建模系列第 10 篇

11th鐵人賽線性規劃

spidyjames

2019-09-11 23:22:49

2202 瀏覽

分享至

接續昨天的內容，我們談到了線性規劃問題是一種凸性規劃問題，而被歸類為凸性規劃問題的好處是，區域最佳解為全域最佳解，且其解必出現在可行解區域的邊界上或頂點。但是，對於線性規劃問題的定義及一些專有名詞，尚未交代，今天就來將這部分補齊。

LP問題的定義

求函數最小值
所有限制條件均為等式限制
所有設計變數皆 $\ge 0$ (非負數)

線性限制條件的型式

三種可能的型式
$a_{i1}y_1 + a_{i2}y_2 + \dots + a_{ik}y_k \le b_i$
$a_{i1}y_1 + a_{i2}y_2 + \dots + a_{ik}y_k = b_i$
$a_{i1}y_1 + a_{i2}y_2 + \dots + a_{ik}y_k \ge b_i$
其中 $b_i$ 稱為resource limits, $b_i \ge 0$ (非負數)
型式轉換

對於 $\le$ 的限制引入slack variable $S_i$ , $S_i \ge 0$
ex: $3y_1 - 2y_2 \le 5 \Rightarrow 3y_1 - 2y_2 + S = 5$
對於 $\ge$ 的限制引入surplus variable $S_i$ , $S_i \ge 0$
ex: $y_1 - 3y_2 \ge 2 \Rightarrow y_1 - 3y_2 - S = 2$

Unrestricted variable

假如一設計變數 $y_i$ 為unrestricted in sign或free in sign，意指 $S_i$ , $S_i \ge 0$ 可為任意變數。此時令 $y_i = {y_i}^{+} - {y_i}^{-}$ ，其中 $y_i^{+} \ge 0$ 且 $y_i^{-} \ge 0$ 皆為新增加的變數。
當 $y_i^{+} > y_i^{-} \Rightarrow y_i > 0$
當 $y_i^{+} < y_i^{-} \Rightarrow y_i < 0$
當 $y_i^{+} = y_i^{-} \Rightarrow y_i = 0$

LP標準化型式

根據周志成老師的說法，我們之所以將問題寫成標準型，主要的原因是為了執行消去法以化簡線性方程組 (消去法不適用於線性不等式)。
min $f(\bar X) = c_1x1 + c_2x_2 + \dots + c_nx_n$
s.t.
$a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1$
$a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2$
$\dots$
$a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m$
其中， $b_i \ge 0$ , $i=1, \dots , m$
$x_j \ge 0$ , $j=1, \dots , n$ , $n > m$
以向量與矩陣型式表示，
min $f(\bar X) = \bar C^{T}\bar X$
s.t.
$\bar A_{m*n} \bar X_{n*1} = \bar b_{m*1}$
$\bar b \ge 0$ , $\bar X \ge 0$ , $\bar A = [a_{ij}]_{m*n}$